package com.zk.algorithm.sort;

/**
 * 插入排序
 *
 * [← 已排序区间 →|← 未排序区间 →]
 *
 * @author zk
 */
public class InsertionSort {

    public void sort(int[] a) {
        int n = a.length;

        if (n <= 1) return;

        // [ 1              ]
        //   ↑
        //   i
        for (int i = 1; i < n; ++i) {
            int value = a[i];
            int j = i - 1;

            // 查找插入的位置
            for (; j >= 0; --j) {
                // [← 已排序区间 →] 的某个 a[j] 值大于当前的这个固定的值 a[i]
                if (a[j] > value) {
                    // 向后移动
                    a[j + 1] = a[j];  // 数据移动
                } else {
                    break;
                }
            }
            // 插入
            a[j + 1] = value; // 插入数据
        }
    }

}
